ON PERMUTATION POLYTOPES

BARBARA BAUMEISTER, CHRISTIAN HAASE, BENJAMIN NILL, AND ANDREAS PAFFENHOLZ

Abstract. In this paper we lay the foundations for the study of permutation polytopes: the convex hull of a group of permutation matrices. We clarify the relevant notions of equivalence, prove a product theorem, and discuss centrally symmetric permutation polytopes. We provide a number of combinatorial properties of (faces of) permutation polytopes. As an application, we classify ≤ 4-dimensional permutation polytopes and the corresponding permutation groups. Classification results and further examples are made available online at [6].

We conclude with several questions suggested by a general finiteness result.

Introduction

One of the most intensively studied convex polytopes is the Birkhoff polytope, also known as the assignment polytope, also known as the polytope of doubly stochastic matrices [4, 7, 10, 11, 12, 23, 27]. It is the convex hull in ℝ^{n×n} of the n × n permutation matrices. This polytope naturally appears in various contexts such as enumerative combinatorics [3, 24], optimization [5, 16, 23, 26], and statistics [23] (and references therein), as well as in representation theory [8, 22], and in the context of the van der Waerden conjecture for the permanent [10].

In the present article, we propose to systematically study general permutation polytopes. These are defined as the convex hull of a subgroup G of the group of n × n permutation matrices. This is a convex geometric invariant of a permutation representation, and it yields various numerical invariants like dimension, volume, diameter, f-vector, etc.

A number of authors have studied special classes of permutation polytopes different from the Birkhoff polytope. Brualdi and Liu [11] compute basic invariants of the polytope of the alternating group; for this polytope, Hood and Perkinson [20] describe exponentially many facets. Collins and Perkinson [13] observe that Frobenius polytopes have a particularly simple combinatorial structure, and Steinkamp [25] adds results about dihedral groups. Most recently, Guralnick and Perkinson [19] investigate general permutation polytopes, their dimension, and their graph.

Main results. In Section 1, we introduce the main objects of our study, representation polytopes and permutation polytopes. We also add a note on 0/1-polytopes, Proposition 1.3, showing that there is only a finite number of lattice equivalence classes of d-dimensional 0/1-polytopes.

2000 Mathematics Subject Classification. Primary 20B35, 52B12; Secondary 05E10, 52B05, 52B20, 90C27.

In Section 2, we discuss notions of equivalence of representations and the associated representation polytopes, respectively permutation polytopes. In particular, we introduce stable and effective equivalence of representations.

In Section 3, we investigate combinatorial properties of permutation polytopes and their faces. In particular, we are interested in the question which polytopes can be realized as faces of permutation polytopes. The first main theorem, Theorem 3.5, says that, if a permutation polytope is combinatorially a product, then the permutation group has a natural product structure. As a second result, we give an explicit construction, Theorem 3.8, showing that pyramids over faces of permutation polytopes appear again as faces of permutation polytopes. Further, we are interested in centrally symmetric faces and polytopes. We show in Theorem 3.10 that free sums of crosspolytopes and cubes occur as faces of permutation polytopes. Finally, we construct in Theorem 3.15 the essentially unique permutation group where the permutation polytope is a crosspolytope.

In Section 4, we use the results from the previous section to classify in Theorem 4.1 up to effective equivalence all permutation representations whose polytopes have dimension ≤ 4. We also start the more difficult classification of combinatorial types of low dimensional polytopes which appear as faces of permutation polytopes. Theorem 4.3 gives a complete answer for dimension ≤ 3, and there remain only two 4-polytopes for which we could not decide whether or not they can be realized. The lists of permutation groups and polytopes can also be found on the webpage [6].

Those examples and classifications suggest a number of open questions and conjectures which we formulate in Section 5.

Remark: Some authors use the notion of permutation polytope differently: the convex hull of a G-orbit in ℝ^{n}. These are linear projections of our permutation polytopes. Examples include the permutahedron, the traveling salesman polytope, or any polytope with a vertex transitive group of automorphisms. They appear in combinatorial optimization problems of various computational complexities [22]. Moreover, orbit polytopes have recently been used to construct resolutions in group cohomology [15].

1. Representation-, permutation-, and 0/1-polytopes

1.1. Polytopes. For a standard reference on polytopes we refer to [28]. A polytope P is the convex hull conv(S) of a finite set of points S in a real vector space V. The dimension dim P is the dimension of the affine hull aff P as an affine space. We say P is a d-polytope, if dim P = d. If V is equipped with a full dimensional lattice Λ and we can choose S ⊂ Λ, then we call P a lattice polytope.

A face F of P (denoted by F ⪯ P) is a subset where some linear functional is maximized. Zero-dimensional faces are vertices, one-dimensional faces are edges, and faces of codimension one are facets. The poset of faces ordered by inclusion is called the face lattice. The vertex set of P is denoted by V(P). The degree of a vertex is the number of edges it is contained in.

There is a hierarchy of equivalence relations on (lattice) polytopes. Two polytopes P ⊂ ℝ^{m} and Q ⊂ ℝ^{n} are affinely equivalent if there is an affine isomorphism of the affine hulls ϕ: aff P → aff Q that maps P onto Q. For lattice equivalence we additionally require that ϕ is an isomorphism of the affine lattices aff P ∩ Λ → aff Q ∩ Λ′. Combinatorial equivalence is merely an equivalence of the face lattices as posets.

lattice equivalent ⇒ affinely equivalent ⇒ combinatorially equivalent

The converse implications do not hold, for examples see [29, Prop. 7].

1.2. Representation polytopes. Let ρ: G → GL(V) be a real representation of the finite group G with identity element e. It induces an ℝ-algebra homomorphism from the group algebra ℝ[G] to End(V), which we also denote by ρ.

Definition 1.1. The representation polytope P (ρ) of the representation ρ is defined as the convex hull of ρ(G) in the vector space End(V).

Notice, that the representation ρ splits as a G-representation over ℂ into irreducible components:

(1.1)  ρ ≅ ∑_{σ∈Irr(G)} c_{σ}σ

with c_{σ} ∈ ℕ for σ in Irr(G), the set of pairwise non-isomorphic irreducible ℂ-representations. We define the set of irreducible factors of ρ,

Irr(ρ) := {σ ∈ Irr(G) : c_{σ} > 0}.

The group G acts on the polytope P (ρ) by left multiplication, inducing an affine automorphism of P (ρ):

g(ρ(h)) = ρ(g)ρ(h) for all g, h ∈ G.

Therefore, since any vertex of P (ρ) has to be contained in ρ(G), and left multiplication on G is regular, thus transitive, we get:

(1.2)  V(P (ρ)) = ρ(G).

Here is one application (the case of equality is treated in Corollary 2.8):

(1.3)  dim P (ρ) ≤ |V(P (ρ))| − 1 ≤ |G| − 1.

In particular, though there are infinitely many representations of finite groups of fixed order, they give rise to only finitely many combinatorial types of representation polytopes. We are going to see a stronger statement in Corollary 1.4.

More implications: All vertices of P (ρ) have the same degree. When considering the combinatorics of a face of P (ρ) we can always assume that it has ρ(e) = id as a vertex. If F is a face of P (ρ) with vertex set V(F) = ρ(U) for U ⊆ G, then F is also a face of the representation polytope P (ρ′), where ρ′: ⟨U⟩ → GL(V). Here ⟨U⟩ denotes the smallest subgroup of G containing U.

1.3. Permutation polytopes. We identify the symmetric group S_{n} on {1, …, n} via the usual permutation representation with the set of n × n permutation matrices, i.e., the set of matrices with entries 0 or 1 such that in any column and any row there is precisely one 1. Throughout, we use cycle notation: For instance (123)(45) ∈ S_{6} denotes the permutation 1 ↦ 2, 2 ↦ 3, 3 ↦ 1, 4 ↦ 5, 5 ↦ 4, 6 ↦ 6. Note that for g_{1}, g_{2} ∈ S_{n} we have g_{1}g_{2} ∈ S_{n}, while g_{1} + g_{2} ∈ Mat_{n}(ℕ). Here, for a set C ⊆ ℂ, we define Mat_{n}(C) as the set of n × n matrices with entries in C. We identify Mat_{n}(ℝ) ≅ ℝ^{n^{2}}, thus we have the usual scalar product, i.e., ⟨A, B⟩ = ∑_{i,j} A_{i,j}B_{i,j} for A, B ∈ Mat_{n}(ℝ).

A subgroup of S_{n} is called permutation group. A faithful representation ρ: G → S_{n} is called permutation representation, thus G can be identified with the permutation group ρ(G). For both situations we often write in short G ≤ S_{n}.

Definition 1.2. For G ≤ S_{n} we define P (G) := conv(G) ⊆ Mat_{n}(ℝ), the permutation polytope associated to G. The convex hull of all permutations B_{n} := P (S_{n}) is called the n^{th} Birkhoff polytope.

In particular, any permutation polytope is a representation polytope, as well as a lattice polytope with respect to the lattice Mat_{n}(ℤ).

1.4. 0/1-polytopes. An important property of permutation polytopes is that they belong to the class of 0/1-polytopes. A 0/1-polytope is the convex hull of points in {0, 1}^{d}. They have been classified up to dimension 6 [1, 2]. For a survey on these well-studied polytopes see [29], where also the following basic fact is shown: any d-dimensional 0/1-polytope is affinely equivalent to a lattice polytope in [0, 1]^{d}. This implies immediately that there are only finitely many affine types of d-dimensional 0/1-polytopes. Even more is true.

Proposition 1.3. Every d-dimensional 0/1-polytope is lattice equivalent to a lattice polytope in the 2^{2^{d}}-dimensional unit cube. In particular, there are only finitely many lattice types of d-dimensional 0/1-polytopes.

This bound is far from optimal. All we care about is that it is finite. We have not found this result in the literature, so we include the proof.

Proof. Every d-dimensional 0/1-polytope is lattice equivalent to a full-di-mensional lattice polytope which will, in general, no longer have 0/1 coordinates. But it still has the property that its vertices are the only lattice points it contains. Such a polytope can have no more than 2^{d} vertices, as two vertices with the same parity would have an integral midpoint.

Now suppose P ⊂ [0, 1]^{N} is a d-dimensional 0/1-polytope with N > 2^{2^{d}}. Then there are two of the N coordinates which agree for every vertex of P, say, P ⊂ {x_{i} = x_{j}}. Thus we can delete the j^{th} coordinate and obtain a lattice equivalent 0/1-polytope ⊂ [0, 1]^{N−1}. □

Corollary 1.4. There are up to lattice equivalence only finitely many permutation polytopes associated to finite groups of fixed order.

This follows from Equation (1.3).

2. Notions of equivalence

Throughout let ρ: G → GL(V) be a real representation.

2.1. Stable equivalence of representations. When working with permutation polytopes, one would like to identify representations that define affinely equivalent polytopes. For instance, this holds for the following five permutation groups: ⟨(1234)⟩ ≤ S_{4}, ⟨(1234)(5)⟩ ≤ S_{5}, ⟨(1234)(56)⟩ ≤ S_{6}, ⟨(1234)(56)(78)⟩ ≤ S_{8}, ⟨(1234)(5678)⟩ ≤ S_{8}. We are now going to introduce a suitable notion of equivalence on the real representations of a finite group. The crucial point is the observation that representation polytopes do not care about multiplicities of irreducible factors in the defining representation. For this let us fix a finite group G.

Definition 2.1. For a representation ρ: G → GL(V) define the affine kernel ker^{∘} ρ as

ker^{∘} ρ := { ∑_{g∈G} λ_{g}g ∈ ℝ[G] : ∑_{g∈G} λ_{g}ρ(g) = 0 and ∑_{g∈G} λ_{g} = 0 }

Say that a real representation ρ′: G → GL(V′) is an affine quotient of ρ if ker^{∘} ρ ⊆ ker^{∘} ρ′ .

Then real representations ρ_{1} and ρ_{2} of G are stably equivalent, if there are affine quotients ρ′_{1} of ρ_{1} and ρ′_{2} of ρ_{2} such that ρ_{1} ⊕ ρ′_{1} ≅ ρ_{2} ⊕ ρ′_{2} as G-representations. For instance, ρ_{1} is stably equivalent to ρ_{1} ⊕ ρ′_{1}.

Example 2.2. Let 1_{G} be the trivial representation of G. We observe that ker^{∘} ρ = ker 1_{G} ∩ ker ρ. Hence, by Equation (1.1)

ker^{∘} ρ = ker 1_{G} ∩ ⋂_{1_{G}≠σ∈Irr(ρ)} ker σ.

Therefore, any real representation ρ′: G → GL(V′) with Irr(ρ′)\{1_{G}} ⊆ Irr(ρ)\{1_{G}} is an affine quotient of ρ. For instance, ρ′ may be the restriction of ρ to an invariant subspace of V.

Proposition 2.3. Suppose ρ and ρ̄ are stably equivalent real representations of a finite group G. Then P (ρ) and P (ρ̄) are affinely equivalent.

Proof. It is enough to show that P (ρ) and P (ρ ⊕ ρ′) are affinely equivalent for an affine quotient ρ′ of ρ.

The projection yields an affine map P (ρ ⊕ ρ′) → P (ρ). In order to construct an inverse, we need a map aff P (ρ) → aff P (ρ′). The obvious choice is to map a point ∑_{g∈G} λ_{g}ρ(g) ∈ aff P (ρ) to ∑_{g∈G} λ_{g}ρ′(g) ∈ aff P (ρ′) (∑_{g∈G} λ_{g} = 1). This is well defined if (and only if) ker^{∘} ρ ⊆ ker^{∘} ρ′. □

A priori, it is often not clear whether two representations are stably equivalent. Here we provide an explicit criterion:

Theorem 2.4. Two real representations are stably equivalent if and only if they contain the same non-trivial irreducible factors.

The proof will be given in the next subsection. We note that we have already seen the if-direction in Example 2.2.

2.2. The dimension formula. To prove Theorem 2.4 we recall the dimension formula of a representation polytope in [19].

The following equation is Theorem 3.2 of [19] (recall that the degree of a representation is the dimension of the vector space the group is acting on).

Theorem 2.5 (Guralnick, Perkinson).

dim P (ρ) = ∑_{1_{G}≠σ∈Irr(ρ)}(deg σ)^{2}.

The proof relies on the Theorem of Frobenius and Schur [14, (27.8-10)] to determine the dimension of ρ(ℂ[G]), and then relates dim P (ρ) to dim_{ℂ}ρ(ℂ[G]) via the following observation which explains the special role of the trivial representation.

Lemma 2.6. The affine hull of P (ρ) does not contain 0 if and only if 1_{G} ∈ Irr(ρ).

Now, we can give the proof of the characterization of stable equivalence:

Proof of Theorem 2.4. It is enough to show that ρ and ρ ⊕ ρ′ have the same non-trivial irreducible factors for an affine quotient ρ′ of ρ.

By Proposition 2.3 P (ρ) and P (ρ ⊕ ρ′) are affinely equivalent. In particular, they have the same dimension. Since any irreducible factor of ρ is an irreducible factor of ρ ⊕ ρ′, the dimension formula Theorem 2.5 implies that any non-trivial irreducible factor of ρ′ already appears as an irreducible factor of ρ. Therefore, ρ and ρ′ have the same non-trivial irreducible factors. □

For an application let us look at the regular representation of a group G. This is the permutation representation reg: G → S_{|G|} via right multiplication. We have Irr(reg) = Irr(G).

Lemma 2.7. P (reg) is a simplex of dimension |G| − 1, and the vertices form a lattice basis of the lattice lin P (reg) ∩ Mat_{|G|}(ℤ).

Proof. For this we enumerate the elements of G as g_{1}, …, g_{|G|} with g_{1} = e. Then for i ∈ {1, …, |G|} the permutation matrix ρ(g_{i}) of size |G|×|G| has in the first row only zeros except one 1 in column i. Hence, the matrices g_{1}, …, g_{|G|} are linearly independent. Moreover, this shows that they form a lattice basis of lin P (reg) ∩ Mat_{|G|}(ℤ). □

The dimension formula and Lemma 2.7 imply another proof of the following well-known equation:

|G| − 1 = dim P (reg) = ∑_{1_{G}≠σ∈Irr(G)}(deg σ)^{2}.

We see that in a special case there is indeed a correspondence between stable equivalence and affine equivalence, this is [19, Cor. 3.3].

Corollary 2.8. Let ρ be a faithful representation. Then P (ρ) is a simplex if and only if ρ is stably equivalent to reg.

Here is an example showing that stably equivalent permutation representations do not necessarily have lattice equivalent permutation polytopes.

Example 2.9. Let G := ⟨(12), (34)⟩ ≤ S_{4}. We define the following permutation representation: ρ: G → S_{6}, by (12) ↦ (12)(34) and (34) ↦ (12)(56). Then P (ρ) is a tetrahedron, and ρ is stably equivalent to the regular representation. However, the vertices of P (ρ) do not form an affine lattice basis of the lattice aff P (reg) ∩ Mat_{|G|}(ℤ), in contrast to P (reg) by Lemma 2.7.

Affine equivalence is the same as lattice equivalence for the sublattice generated by the vertices. The previous example shows that lattice equivalence for the whole lattice Mat_{n}(ℤ) is a more subtle condition. This relation deserves further study.

2.3. Effective equivalence of representations. The following example illustrates that stable equivalence is too rigid.

Example 2.10. Let G := ⟨(12), (34)⟩ ≤ S_{4}. Then ρ_{1} : G ↪ S_{4} is a permutation representation with P (G) = P (ρ_{1}) a square. On the other hand, we define another permutation representation ρ_{2} : G → S_{4}, by (12) ↦ (12) and (34) ↦ (12)(34). Then P (ρ_{2}) is the same square. However, ρ_{1} and ρ_{2} are not stably equivalent, since they do not have the same irreducible factors.

We observe that these two representations ρ_{1}, ρ_{2} : G → GL(V) are conjugated, i.e., there exists an automorphism ψ of G such that ρ_{2} = ρ_{1} ∘ ψ. Hence, since ρ_{1}(G) = ρ_{2}(G), we have P (ρ_{1}) = P (ρ_{2}). However, conjugation permutes the irreducible factors, thus does not respect stable equivalence. To avoid this ambiguity we propose the following notion.

Definition 2.11. Two real representations ρ_{i}: G_{i} → GL(V_{i}) (for i = 1, 2) of finite groups are effectively equivalent, if there exists an isomorphism ϕ: G_{1} → G_{2} such that ρ_{1} and ρ_{2}∘ϕ are stably equivalent G_{1}-representations.

Moreover, we say G_{1} ≤ S_{n_{1}} and G_{2} ≤ S_{n_{2}} are effectively equivalent permutation groups, if G_{1} ↪ S_{n_{1}} and G_{2} ↪ S_{n_{2}} are effectively equivalent permutation representations.

By Theorem 2.4 we may put this definition in a nutshell: Two permutation groups are effectively equivalent if they are isomorphic as abstract groups such that via this isomorphism the permutation representations contain the same non-trivial irreducible factors.

In particular, effectively equivalent representations have affinely equivalent representation polytopes by Proposition 2.3. Of course, in general the converse cannot hold, since by Lemma 2.7 permutation groups that are not even isomorphic as abstract groups still may have affinely equivalent permutation polytopes. However, the following question remains open.

Question 2.12. Are there permutation groups G_{1}, G_{2} that are isomorphic as abstract groups and whose permutation polytopes P (G_{1}) and P (G_{2}) are affinely equivalent, while G_{1} and G_{2} are not effectively equivalent?

By Theorem 4.1 there are no such permutation groups, if their permutation polytopes have dimension ≤ 4.

3. The combinatorics of permutation polytopes

Throughout, G ≤ S_{n} is a permutation group. By G ≅ H we denote an (abstract) group isomorphism.

3.1. The smallest face containing a pair of vertices.

In [10, 11] the diameter of the edge-graph of B_{n} and P (A_{n}) was bounded from above by 2. Later this could be generalized in [19] to permutation polytopes associated to transitive permutation groups. For this, Guralnick and Perkinson needed a crucial observation, that we are going to recall here.

Definition 3.1. Let e ≠ g ∈ G.

• The support supp(g) is the complement of the set of fixed points.

• We denote by F_{g} the smallest face of P (G) containing e and g.

• We denote by g = z_{1} ∘⋯∘z_{r} the unique disjoint cycle decomposition of g in S_{n}, i.e., z_{1}, …, z_{r} are cycles with pairwise disjoint support, and g = z_{1} ⋯ z_{r}.

• Let g = z_{1} ∘ ⋯ ∘ z_{r}. For h ∈ S_{n} we say h is a subelement of g, if there is a subset I ⊆ {1, …, r} such that h = ∏_{i∈I} z_{i}.

• g is called indecomposable in G, if e and g are the only subelements of g in G.

The following result is Theorem 3.5 in [19]. We include the very instructive proof here.

Theorem 3.2 (Guralnick, Perkinson). Let g ∈ G. The vertices of F_{g} are precisely the subelements of g in G. In particular, e and g form an edge of P (G) if and only if g is indecomposable in G.

Therefore, the number of indecomposable elements (different from e) in G equals the degree of any vertex of P (G).

Remark 3.3. The proof of Guralnick and Perkinson uses a simple but effective way of defining certain faces of a permutation polytope P (G) for G ≤ S_{n}. These faces are the intersections of P (G) with faces of the Birkhoff polytope P (S_{n}). Since this method will also be used for several results of this paper, we give here the explicit description.

Let S ⊆ S_{n} be a subset of permutation matrices. We define the n × nmatrix M(S) := max(σ : σ ∈ S), where the maximum is applied for any entry. Then M(S) has only entries in {0, 1}, thus ⟨M(S), g⟩ ≤ n for any g ∈ G. Therefore, F (S) := {g ∈ G : ⟨M(S), g⟩ = n} is a face of P (G). If S ⊆ G, then S ⊆ V(F (S)).

If S ⊆ G and |S | ≤ 2, then F (S) is even the smallest face of P (G) containing S. This is part of the proof of Theorem 3.2.

While in the case of Birkhoff polytopes this implication holds also for |S | ≥ 3, it is important to note that in the case of general permutation polytopes it usually fails. The following example illustrates this phenomenon. Let z_{1} := (12), z_{2} := (34), z_{3} := (56), z_{4} := (78). We define G := ⟨z_{1}z_{2}, z_{1}z_{3}, z_{1}z_{4}⟩ ≤ S_{8}, and S := {e, z_{1}z_{2}, z_{1}z_{3}}. Then P (G) is a four-dimensional crosspolytope, i.e., the dual is a 4-cube, and P (G) contains a face with vertices S. However, F (S) also contains the vertex z_{2}z_{3}, so it is not the smallest face of P (G) containing S.

Proof of Theorem 3.2. Let S := {e, g} ⊆ G, and F (S) the face of P (G) as defined in the previous remark. Then the vertices of F (S) are precisely the subelements of g in G. On the other hand, let g = z_{1} ∘ ⋯ ∘ z_{r}, and h = z_{1}∘⋯∘z_{s} (s ≤ r) be a subelement of g in G. Then h′ := gh^{−1} = z_{s+1}∘⋯∘z_{r} is also a subelement of g in G. Now, the following identity of matrices holds:

e + g = h + h′.

Therefore, F (S) is centrally symmetric with center (e + g)/2. Hence, F (S) is the smallest face F_{g} of P (G) containing S = {e, g}. □

In particular we see from the proof that, if g ∈ G and h ∈ V(F_{g}), then the antipodal vertex of h in the centrally symmetric face F_{g} is given by gh^{−1} with supp(h) ∩ supp(gh^{−1}) = ∅. Let us note this important restriction on the combinatorics of a permutation polytope.

Corollary 3.4. The smallest face containing a given pair of vertices of a permutation polytope is centrally symmetric.

This generalizes the well-known fact (e.g., see [7, Thm. 2.5]) that the smallest face of the Birkhoff polytope containing a pair of vertices is a cube. This strong statement is not true for general permutation polytopes. For instance in Corollary 3.11 we show that crosspolytopes appear as faces of permutation polytopes.

3.2. Products. Products of permutation polytopes are again permutation polytopes, and therefore also products of faces of permutation polytopes appear as faces of permutation polytopes.

In many cases, given a permutation group G and its permutation polytope P (G), we would like to know all the permutation groups H such that P (H) is combinatorially equivalent to P (G). In the case of products the following result shows that we can reduce this question to each factor.

Theorem 3.5. P (G) is a combinatorial product of two polytopes Δ_{1} and Δ_{2} if and only if there are subgroups H_{1} and H_{2} in G such that

(a) P (H_{i}) is combinatorially equivalent to Δ_{i} for i = 1, 2,

(b) supp(H_{1}) ∩ supp(H_{2}) = ∅,

(c) G = H_{1} × H_{2}.

Proof. The if-part is easy to see. We have to prove the only-if part.

Let G ≤ S_{n}. By assumption, there is a map v from the vertex set V(P (G)) = G to V(Δ_{1} × Δ_{2}) = V(Δ_{1}) × V(Δ_{2}), inducing an isomorphism between the face lattices of P (G) and of Δ := Δ_{1} × Δ_{2}, which we also denote by v. Hence, any element g ∈ G can be labeled as v(g) = (v_{1}(g), v_{2}(g)) ∈ V(Δ) for unique vertices v_{1}(g) ∈ V(Δ_{1}) and v_{2}(g) ∈ V(Δ_{2}). We write v(e) =: (e_{1}, e_{2}), and define H_{1} := {g ∈ G : v_{2}(g) = e_{2}}, as well as H_{2} := {g ∈ G : v_{1}(g) = e_{1}}.

We claim

(3.1)  supp(H_{1}) ∩ supp(H_{2}) = ∅.

Let h_{1} ∈ H_{1} and h_{2} ∈ H_{2}. We have v(h_{1}) = (x_{1}, e_{2}) and v(h_{2}) = (e_{1}, x_{2}) for x_{1} ∈ V(Δ_{1}) and x_{2} ∈ V(Δ_{2}). For i = 1, 2 let us denote by F_{i} the smallest face of Δ_{i} containing e_{i} and x_{i}. Let us define g ∈ G with v(g) = (x_{1}, x_{2}). Since P (G) is via v combinatorially equivalent to Δ, the face F_{1} × F_{2} ≺ Δ is the smallest face of Δ containing v(e) and v(g).

By Corollary 3.4 the face F_{g} ≺ P (G), satisfying v(F_{g}) = F_{1} × F_{2}, is centrally symmetric, and h′_{1} := gh_{1}^{−1} ∈ G is the antipodal vertex to h_{1}. Since supp(h_{1}) ∩ supp(h′_{1}) = ∅, it suffices to show h_{2} = h′_{1}.

Since x_{1} × F_{2} is the smallest face of Δ containing v(h_{1}) and v(g), we get by central symmetry of F_{g} that the smallest face of Δ containing v(h′_{1}) and v(e) has also |V(F_{2})| vertices, thus |V(F_{h′_{1}})| = |V(F_{2})| = |V(F_{h_{2}})|. Note that by Theorem 3.2 h_{1}, h_{2} and h′_{1} are subelements of g, thus determined by their support.

Now, there are two cases, since supp(g) = supp(h_{1}) ⊔ supp(h′_{1}) (here ⊔ denotes the disjoint union).

(1) supp(h′_{1}) ⊆ supp(h_{2}):

Then h′_{1} is a subelement of h_{2}. However, |V(F_{h′_{1}})| = |V(F_{h_{2}})| implies F_{h′_{1}} = F_{h_{2}}. Therefore, h_{2} is also a subelement of h′_{1}, thus h_{2} = h′_{1}, as desired.

(2) supp(h_{1}) ∪ supp(h_{2}) ⊊ supp(g):

As in Remark 3.3 for S := {e, h_{1}, h_{2}} we define the matrix M(S) and the face F (S) of P (G). Since F_{1} × F_{2} is the smallest face of Δ containing v(e), v(h_{1}), v(h_{2}), we get F_{g} ⊆ F (S). However, by our assumption there exists some i ∈ supp(g) with i ∉ supp(h_{1}) ∪ supp(h_{2}). Therefore, the only non-zero entry in the ith-row of M(S) is on the diagonal, while the ith diagonal entry of the permutation matrix g is zero. Hence, ⟨M(S), g⟩ < n, a contradiction.

This proves the claim (3.1).

Hence, |H_{1}H_{2} | = |H_{1} ||H_{2} | = |V(Δ_{1})||V(Δ_{2})| = |V(P (G))| = |G|. Therefore, H_{1}H_{2} = G. Moreover, this implies that H_{1} consists precisely of all elements of G that have disjoint support from all elements in H_{2}, hence is a subgroup. The analogous argument holds for H_{2}. Finally, P (G), P (H_{1}) × P (H_{2}), and Δ_{1} × Δ_{2} are combinatorially equivalent. □

As an application we classify those permutation groups whose d-dimen-sional permutation polytopes have the maximal number of vertices.

Corollary 3.6. Let d := dim P (G). Then

log_{2} |G| ≤ d ≤ |G| − 1,

or equivalently

d + 1 ≤ |G| ≤ 2^{d}.

Moreover the following statements are equivalent:

(1) |G| = 2^{d}, (2) P (G) is combinatorially a d-cube,

(3) P (G) is lattice equivalent to [0, 1]^{d},

(4) G is effectively equivalent to ⟨(12), ⋯, (2d−1 2d)⟩ ≤ S_{2d}.

Proof. As was noted before, P (G) is as a d-dimensional 0/1-polytope that is combinatorially equivalent to a lattice subpolytope of [0, 1]^{d}. Hence we get the inequalities. Moreover, it holds (1) ⇔ (2), (3) ⇒ (2) and (4) ⇒ (2). From Theorem 3.5 (in particular, statement (b)) we deduce (2) ⇒ (3) and (2) ⇒ (4). □

Here is another application of Theorem 3.5. For this note that by Theorem 3.2 a permutation polytope P (G) is simple if and only if there are dimension many indecomposable elements in G. Now, the main result of [21] states that any simple 0/1-polytope is a product of simplices. Therefore we can deduce from this geometric statement using Corollary 2.8 a result in representation theory (since the dimension of P (G) can be computed from the irreducible factors by Theorem 2.5). Corollary 3.7. Let ρ be a permutation representation of a group G. If G contains precisely dim P (ρ) many indecomposable elements, then G is the product of subgroups H_{1}, …, H_{l} with mutually disjoint support, where ρ restricted to any H_{i} (i = 1, …, l) is stably equivalent to the regular representation of H_{i}.

3.3. Pyramids. In experiments one observes that most faces of permutation polytopes are actually pyramids over lower dimensional faces. Here, we prove that for any face F of a permutation polytope there exists a permutation polytope having a face that is combinatorially a pyramid over F. Theorem 3.8. Let G ≤ S_{n}. Then there is a permutation group E ≤ S_{2n}, with E ≅ G × ℤ_{2}, such that there is a face of P (E) which is combinatorially a pyramid over P (G).

Proof. Let G ≤ S_{n}. Embedding the product of permutation groups S_{n} × S_{n} into S_{2n}, we define H := {(σ, σ) : σ ∈ G} ≤ S_{2n}. Then H is a subgroup of S_{2n}, and effectively equivalent to G. We define an involution

p := (1 n+1) (2 n+2) ⋯ (n 2n) ∈ S_{2n}.

Then p commutes with each element in H, moreover H ∩ ⟨p⟩ = {e}. Hence, E := H⟨p⟩ is a subgroup of S_{2n} and isomorphic to H × ⟨p⟩. For S := H ⊔ {p} ⊆ E we define as in Remark 3.3 the 2n × 2n-matrix M(S) defining a face F (S) of P (E). We claim that F (S) is a pyramid over conv(H).

First let us show that V(F (S)) = S. Assume that there is some hp ∈ F (S) with h ≠ e. Let h = (σ, σ) for σ ∈ G, σ ≠ e. Assume σ maps 1 to 2. Then hp maps 1 to n + 2. However, this implies that ⟨M(S), hp⟩ < 2n, a contradiction.

Now, it remains to show that H is the set of vertices of a face of F (S). As in Remark 3.3 we define the face F (H) of P (E). By construction p ∉ F (H). Then F (H) ∩ F (S) is a face of F (S) which contains H but not p. □ Corollary 3.9. Pyramids over faces of permutation polytopes appear as faces of permutation polytopes.

3.4. Free sums. Recall that free sums are the combinatorially dual operation to products. For instance the free sum of d intervals is a d-crosspolytope, i.e., the centrally symmetric d-polytope with the minimal number 2d of vertices.

In general we cannot expect that free sums of arbitrary faces of permutation polytopes are again faces of permutation polytopes. Corollary 3.4 shows that already faces that are bipyramids have to be necessarily centrally symmetric. However, we can explicitly construct the following centrally symmetric polytopes as faces.

Theorem 3.10. Let l, d be natural numbers. There exists a face of a permutation polytope that is combinatorially the free sum of an l-crosspolytope and a d-cube.

Proof. Since for l ≥ 1 an l-crosspolytope is the free sum of an (l − 1)- crosspolytope and a 1-cube, we may assume l, d ≥ 1. We set n_{0} := 3d. Let z_{1}, …, z_{d} ∈ S_{n_{0}} be disjoint 3-cycles. We define G_{0} := ⟨z_{1}, …, z_{d}⟩, an elementary abelian 3-group of order 3^{d}. It contains g_{0} := z_{1} ⋯ z_{d}. Let V_{0} := {z_{1}^{k_{1}} ⋯ z_{d}^{k_{d}} : k_{i} ∈ {0, 1}}. This is precisely the set of subelements of g_{0} in G_{0}, hence, by Theorem 3.2 V_{0} is the vertex set of a face F_{0} of P (G_{0}). This face F_{0} is combinatorially a d-cube.

Now, we proceed by induction for i = 1, …, l. We define

n_{i} := 2n_{i−1}, H_{i} := {(g, g) : g ∈ G_{i−1}} ≤ S_{n_{i}}, g_{i} := (g_{i−1}, g_{i−1}) ∈ H_{i},

p_{i} := (g_{i−1}, e) ∈ S_{n_{i}}, p′_{i} := (e, g_{i−1}) ∈ S_{n_{i}}, G_{i} := H_{i}⟨p_{i}⟩ ≤ S_{n_{i}}. Note that H_{i}, G_{i} are elementary abelian 3-groups. Moreover, G_{i} ≅ H_{i} ×⟨p_{i}⟩. Let V_{i} be the set of subelements of g_{i} in G_{i}, and F_{i} the smallest face of P (G_{i}) containing e and g_{i}, thus V_{i} is the vertex set of F_{i} by Theorem 3.2. By induction hypothesis we know that F_{i−1} is combinatorially the free sum of an i−1-crosspolytope and a d-cube. We show that F_{i} is a bipyramid over F_{i−1} with apexes {p_{i}, p′_{i}}. We claim

(3.2)  V_{i} = {(v, v) : v ∈ V_{i−1}} ⊔ {p_{i}, p′_{i}}.

Let (v, v′) ∈ V_{i}. Then v, v′ are subelements of g_{i−1} in G_{i−1}. Assume v ≠ v′, in particular (v, v′) ∉ H_{i}. Since (v, v′) ∈ G_{i} and p_{i} has order three, we have either (i) (v, v′) = hp_{i} or (ii) (v, v′) = hp_{i}^{−1} for some h ∈ H_{i}. Let h = (g, g) for g ∈ G_{i−1}. This yields either (v, v′) = (gg_{i−1}, g) or (v, v′) = (gg_{i−1}^{−1}, g), in particular, g = v′ is a subelement of g_{i−1}. Now, the case (i) implies g = e, thus (v, v′) = p_{i}, since otherwise gg_{i−1} cannot be a subelement of g_{i−1}, because g_{i−1} decomposes into disjoint 3-cycles by construction. In the case (ii) we see analogously g = g_{i−1}, thus (v, v′) = p′_{i}. This proves the claim (3.2).

Since by Corollary 3.4 F_{i} is centrally symmetric with antipodal vertices p_{i} and p′_{i}, and since p_{i}, p′_{i} ∉ aff H_{i} by construction, the claim implies that the face F_{i} is a bipyramid over the convex hull of all elements (v, v) (for v ∈ V_{i−1}), which is affinely equivalent to F_{i−1}. □

Corollary 3.11. For any dimension d there is a face of a permutation polytope that is a d-crosspolytope.

Example 3.12. As an illustration of the proof of Theorem 3.10, we show how to obtain the octahedron as a face of a permutation polytope. The octahedron is the free sum of an interval and a square, so l = 1 and d = 2. Therefore, we define z_{1} := (123), z_{2} := (456), and G_{0} := ⟨z_{1}, z_{2}⟩ ≤ S_{6}. Now, we set z′_{1} := (789), z′_{2} := (10 11 12), and G_{1} := ⟨z_{1}z′_{1}, z_{2}z′_{2}, z_{1}^{−1}z_{2}z′_{1}⟩ ≤ S_{12}. Then for g_{1} := z_{1}z_{2}z′_{1}z′_{2} the face F_{1} := F_{g_{1}} of P (G) is an octahedron with the vertex set V_{1} = {e, z_{1}z′_{1}, z_{2}z′_{2}, z_{1}z_{2}z′_{1}z′_{2}, z_{1}z_{2}, z′_{1}z′_{2}}.

3.5. Centrally symmetric permutation polytopes. We will establish a one-to-one correspondence between centrally symmetric permutation polytopes on one hand and certain subspaces of 𝔽_{2}^{r} on the other. We will liberally identify sets I ⊆ [r] := {1, …, r} with their incidence vectors I ∈ 𝔽_{2}^{r}.

Suppose P (G) is centrally symmetric, and let g_{0} = z_{1} ∘ ⋯ ∘ z_{r} ∈ G be the vertex opposite to e. Then P (G) = F_{g_{0}}, and by Theorem 3.2, every element of G is a subelement of g_{0}. Applied to g_{0}^{−1} = z_{1}^{−1} ∘ ⋯ ∘ z_{r}^{−1} this yields that for i = 1, …, r we have z_{i}^{−1} = z_{i}, so that z_{i} is a cycle of length two. Hence, the elements of G have order two. They can be written as z_{I} := Π_{i∈I}z_{i} for certain I ⊆ [r]. (For example, z_{∅} = e, and z_{[r]} = g_{0}.)

Multiplication in G corresponds to addition (symmetric difference) in 𝔽_{2}^{r}. This means that the set of I such that z_{I} ∈ G is a subspace of 𝔽_{2}^{r}. Conversely, given such a subspace containing the all-ones-vector [r], we obtain a centrally symmetric permutation polytope. We have just proved the second part of the following proposition. The first part follows from Corollary 3.4.

Proposition 3.13. P (G) is centrally symmetric if and only if there is a pair of vertices such that P (G) is the smallest face containing them.

In this case, G is an elementary abelian 2-group, in particular the number of vertices of P (G) is a power of two.

If G is an elementary abelian 2-group, P (G) does not have to be centrally symmetric, see Theorem 4.1.

Continuing our discussion of centrally symmetric permutation polytopes, we can reorder the elements of [n] (G ⊆ S_{n}) so that the matrices in G are block diagonal with blocks ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) or ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) (plus n−2r blocks (1)). Projecting to the r upper right entries of the 2 × 2 blocks is a lattice isomorphism to ℤ^{r}. Reduction mod 2 yields, again, our subspace.

Proposition 3.14. If P (G) is centrally symmetric, then the free sum of P (G) with itself is again a permutation polytope.

Proof. Suppose P (G) is centrally symmetric with corresponding subspace V ⊆ 𝔽_{2}^{r}. Define a new subspace

Ṽ := {(I, I) : I ∈ V } ∪ {(I, [r] − I) : I ∈ V } ⊂ 𝔽_{2}^{r} × 𝔽_{2}^{r}

We claim that the permutation polytope P (G̃) of the corresponding permutation group G̃ realizes the free sum of P (G) with itself.

We work with the 2r upper right entries (x, y) ∈ ℝ^{r} × ℝ^{r}. Both, the diagonal embedding x ↦ (x, x) and the “anti-diagonal” embedding x ↦ (x, 1 − x) include P (G) into P (G̃) and exhaust all vertices. Their images intersect in the unique common interior point \frac{1}{2}(1, 1). □

While in any dimension d there exists a permutation polytope which is a d-cube, this is not true for its combinatorial dual, the d-dimensional crosspolytope.

Theorem 3.15. There is a d-dimensional permutation polytope P (G) that is combinatorially a crosspolytope if and only if d is a power of two. In this case, the effective equivalence class of G is uniquely determined.

Proof. The fact that d must be a power of two follows from Proposition 3.13. In that case, existence follows from Proposition 3.14. So we only need to show uniqueness.

Let G be a permutation group such that P (G) is a d-dimensional crosspolytope, d = 2^{k}. Then |G| = 2^{k+1}, and our subspace V ⊂ 𝔽_{2}^{r} has dimension k + 1. Choose generators g_{0}, g_{1}, …, g_{k} of G, i.e., a basis of V. Consider the k × r matrix with rows g_{1}, …, g_{k} ∈ 𝔽_{2}^{r}. If there are two equal columns i, j then we can omit z_{i} without changing the effective equivalence class. On the other hand, there can be at most 2^{k} different columns. As remarked above, we can embed P (G) ↪ ℝ^{r}. So, in particular, r ≥ d = 2^{k}. Hence, r = d, and this matrix simply lists all possible 0/1 vectors. It is, up to permutation of the columns, uniquely defined. □

Example 3.16. From the proof we get an explicit description of the permutation groups defining d-dimensional crosspolytopes. For instance, let d = 4. Since r = d = 4, we have g_{0} = z_{1}∘z_{2}∘z_{3}∘z_{4}, where we may choose z_{1} = (12), z_{2} = (34), z_{3} = (56), z_{4} = (78). Since k = 2, we get G = ⟨g_{0}, g_{1}, g_{2}⟩, where g_{1} and g_{2} are given by the rows of the following matrix consisting of all possible vectors in {0, 1}^{2}:

(\begin{matrix}0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{matrix})

So, g_{1} = z_{2}z_{4}, g_{2} = z_{3}z_{4}, and G = ⟨(12)(34)(56)(78), (34)(78), (56)(78)⟩.

4. Classification results in low dimensions

4.1. Classification of ≤ 4-dimensional permutation polytopes. We would like to classify all permutation polytopes of given small dimension d. For this we take a look at the list of Aichholzer [2] of combinatorial types of 0/1-polytopes in small dimension. For any such 0/1-polytope we first check whether it has constant vertex degree and satisfies the condition of Corollary 3.4. Then we go through the list of groups of size equal to the given number of vertices. Now, using the theoretical results of the previous section we can deduce from the combinatorial structure of the polytope whether this polytope can be realized as a permutation polytope, and even determine all respective permutation groups up to effective equivalence.

Theorem 4.1. Table 1 contains the list of all permutation groups G with ddimensional permutation polytope P (G) for d ≤ 4 up to effective equivalence.

Combin. type of P (G) Isom. type of G Effective equiv. type of G
triangle  ℤ/3ℤ  ⟨(123)⟩
square  (ℤ/2ℤ)^{2}  ⟨(12), (34)⟩
tetrahedron  ℤ/4ℤ  ⟨(1234)⟩
tetrahedron  (ℤ/2ℤ)^{2}  ⟨(12)(34), (13)(24)⟩
triangular prism  ℤ/6ℤ  ⟨(12), (345)⟩
cube  (ℤ/2ℤ)^{3}  ⟨(12), (34), (56)⟩
4-simplex  ℤ/5ℤ  ⟨(12345)⟩
B_{3}  S_{3}  ⟨(12), (123)⟩
prism over tetrahedron ℤ/2ℤ × ℤ/4ℤ ⟨(1234), (56)⟩
prism over tetrahedron (ℤ/2ℤ)^{3}  ⟨(12)(34), (13)(24), (56)⟩
4-crosspolytope  (ℤ/2ℤ)^{3}  ⟨(12)(34), (34)(78), (56)(78)⟩
product of triangles  (ℤ/3ℤ)^{2}  ⟨(123), (456)⟩
prism over triang. prism ℤ/6ℤ × ℤ/2ℤ ⟨(12), (345), (67)⟩
4-cube  (ℤ/2ℤ)^{4}  ⟨(12), (34), (56), (78)⟩

Table 1: Permutation polytopes in dimension ≤ 4

Proof. d = 2: The triangle and the square are the only two-dimensional 0/1-polytopes. If P (G) is a triangle, then use Corollary 2.8. If P (G) is a square, then use Corollary 3.6.

d = 3: There are 4 combinatorial types of three-dimensional 0/1-polytopes with constant vertex degree satisfying the condition of Corollary 3.4.

(1) P (G) is a tetrahedron: Then use Corollary 2.8.

(2) P (G) is a triangular prism: Then use Theorem 3.5.

(3) P (G) is an octahedron: Then |G| = 6, however by Proposition 3.13 |G| has to be a power of two, a contradiction.

(4) P (G) is a cube: Then use Corollary 3.6.

d = 4: There are 9 combinatorial types of four-dimensional 0/1-polytopes with constant vertex degree satisfying the condition of Corollary 3.4.

(1) P (G) is a 4-simplex: Then use Corollary 2.8.

(2) P (G) is combinatorially equivalent to the Birkhoff polytope B_{3} =

P (S_{3}). Then |G| = 6. There are two cases:

If G ≅ ℤ/6ℤ, then either G is generated by an element of order 6, thus G is effectively equivalent to ⟨(123456)⟩ ≤ S_{6}, or G is generated by two elements of orders 2 and 3. In the latter case, the two elements necessarily have disjoint support, since G is abelian. In the first case P (G) is a 5-simplex, in the second case P (G) is a prism. Both cases yield contradictions.

Hence, G ≅ S_{3}. Now, Irr(S_{3}) = {1_{S_{3}}, ρ_{1}, ρ_{2}} with deg ρ_{1} = 1 and deg ρ_{2} = 2. By the dimension formula the permutation representation ρ associated to the permutation group G can only have ρ_{2} as an irreducible factor. Therefore, Theorem 2.4 implies that G is effectively equivalent to ⟨(12), (123)⟩.

(3) P (G) is a prism over a tetrahedron: Use Theorem 3.5 and the classification for d = 3.

(4) P (G) is a 4-crosspolytope: See Example 3.16.

(5) P (G) is a product of two triangles: Use Theorem 3.5.

(6) P (G) is a prism over the triangular prism: Use Theorem 3.5 and the classification for d = 3.

(7) P (G) is a 4-cube: Use Corollary 3.6.

(8) P (G) is a prism over the octahedron: Then Proposition 3.13 yields that the number of vertices has to be a power of two, but P (G) has 12 vertices, a contradiction.

(9) P (G) is a hypersimplex: Any vertex is contained in precisely three facets that are octahedra. Since the inversion map on G is given by the transposition map on P (G), it induces an automorphism of P (G) of order two, and hence, since 3 is odd, there has to be an octahedron F that contains e and whose vertex set is invariant under inversion.

Let g be the unique vertex of F opposite to e. Hence, g is fixed by the inversion map, so g = g^{−1}. As already noted in the proof of Proposition 3.13, this yields that any vertex of F = F_{g} (besides e) has order two, so there are at least five elements of order two in G. On the other hand, since 5 divides |G| = 10, there exists a subgroup of order 5, so we conclude that there are precisely four elements of G that have order 5.

Now take F′ (≠ F) as one of the other two octahedra that contain e. We denote by h the unique vertex h (≠ g) in F′ opposite to e. As just seen, the order of h has to be 5. Since h has to be a product of disjoint cycles of order 5, any subelement of h (≠ e) also has order 5, so by Theorem 3.2 there are at least five vertices of F′ = F_{h} of order 5, a contradiction. □

Remark 4.2. Another approach following Theorem 2.4 and Corollary 3.6 would be to determine all abstract groups G of order ≤ 2^{d} and to calculate the finite set Irr(G). Then for any subset S ⊆ Irr(G) it would be enough to find, if possible, some permutation representation ρ with Irr(ρ) = S. However, the last task seems to be neither practically nor theoretically easy to achieve, compare [9].

4.2. Classification of ≤ 4-dimensional faces. Compared to the classification of permutation polytopes the question whether a given 0/1-polytope is combinatorially equivalent to the face of some permutation polytope is much more difficult. If the answer is supposed to be positive, then one has to construct an explicit permutation group, the dimension of whose permutation polytope might increase dramatically. A systematic way to perform this task is yet to be discovered. However, to show that the answer is negative is even more challenging, since we lack good combinatorial obstructions of the type given in Corollary 3.4.

Theorem 4.3. The following list contains all combinatorial types of ddimensional 0/1-polytopes for d ≤ 4 that may possibly appear as faces F of some permutation polytope P (G): d = 2: There are 2 combinatorial types realized as F: triangle and square.

Both appear as faces of Birkhoff polytopes. d = 3: There are 5 combinatorial types realized as F: tetrahedron, square

pyramid, triangular prism, cube, and octahedron. The first four appear as faces of Birkhoff polytopes.

d = 4: There are 21 combinatorial types that may possibly appear as F:

(a) 11 of these appear as faces of Birkhoff polytopes: 4-simplex, pyramid over square pyramid, Birkhoff polytope B_{3} (free sum of two triangles), pyramid over prism over triangle, wedge W over base edge of square pyramid, pyramid over cube, prism over tetrahedron, product of two triangles, prism over square pyramid, product of triangle and square, 4-cube.

(b) 8 of these can be realized as F: 4-crosspolytope, prism over octahedron, pyramid over octahedron, bipyramid over cube, wedge over the facet of an octahedron, dual of W (see (a)), hypersimplex (the combinatorial type of {x ∈ [0, 1]^{5} : ∑_{i=1}^{5} x_{i} = 2}), and one special 0/1-polytope P.

(c) 2 of these are given by special 0/1-polytopes Q_{1}, Q_{2}, where it is unknown, if they have a realization as F.

The description of the combinatorial types of P, Q_{1}, Q_{2} can be found in Table 2.

Proof. By [7] any d-dimensional face F of some Birkhoff polytope is already realized in B_{2d}. Hence, by looking at the faces of B_{6}, B_{8}, we find all combinatorial types of ≤ 4-dimensional faces of Birkhoff polytopes.

Let us now consider the general case of a d-dimensional face of a permutation polytope.

Table 2: Vertex-Facet-Incidences of P, Q_{1}, Q_{2}

P: f-vector (8, 21, 22, 9) ; [ 0 2 5 6 ] [ 0 2 4 6 ] [ 0 1 2 3 4 ] [ 0 1 2 3 5 ] [ 1 3 4 7 ] [ 1 3 5 7 ] [ 2 3 4 6 7 ] [ 2 3 5 6 7 ] [ 0 1 4 5 6 7 ] Q_{1}: f-vector (7, 19, 23, 11) ; [ 0 1 2 3 4 ] [ 1 2 3 4 5 ] [ 0 1 2 5 ] [ 1 3 5 6 ] [ 0 1 3 6 ] [ 0 1 5 6 ] [ 0 2 5 6 ] [ 2 4 5 6 ] [ 0 2 4 6 ] [ 3 4 5 6 ] [ 0 3 4 6 ] Q_{2}: f-vector (8, 25, 32, 15) ; [ 0 1 2 3 4 5 ] [ 2 4 5 6 ] [ 1 3 5 6 ] [ 1 2 5 6 ] [ 0 1 2 6 ] [ 0 1 3 7 ] [ 0 1 6 7 ] [ 0 2 6 7 ] [ 0 2 4 7 ] [ 0 3 4 7 ] [ 2 4 6 7 ] [ 1 3 6 7 ] [ 3 5 6 7 ] [ 4 5 6 7 ] [ 3 4 5 7 ]

d = 2: The triangle and the square are the only two-dimensional 0/1polytopes.

d = 3: There are 5 combinatorial types of three-dimensional 0/1-polytopes that satisfy the condition of Corollary 3.4. Since the first four are realized as Birkhoff polytopes, we only have to deal with the octahedron. This was done in Example 3.12.

d = 4: There are 21 combinatorial types of four-dimensional 0/1-polytopes that satisfy the condition of Corollary 3.4. Of these, 11 can be realized as faces of Birkhoff polytopes. Here are the remaining 10 cases:

(1) The 4-crosspolytope: See Table 1.

(2) The prism over an octahedron: The octahedron is a face of a permutation polytope, so also the prism is.

(3) Pyramid over octahedron: See Corollary 3.9 and the classification for d = 3.

(4) Bipyramid over cube: See Theorem 3.10.

(5) The dual of W: Let a_{1}, a_{2}, a_{3}, a_{4}, b_{1}, b_{2}, b_{3}, b_{4} be eight 3-cycles with pairwise disjoint support, realized as elements in S_{24}. Let e_{1} be an involution that exchanges a_{1} and a_{2}, i.e., for a_{1} = (123) and a_{2} = (456), we define e_{1} := (14)(25)(36). In the same way we define e_{2} as the involution exchanging b_{1} and b_{2}, and d_{1} exchanging a_{3} and a_{4}, and d_{2} exchanging b_{3} and b_{4}. Then we define v_{1} := a_{1}a_{2}a_{3}a_{4}, v_{2} := b_{1}b_{2}b_{3}b_{4}, v_{3} := d_{1}d_{2}, and v_{4} := e_{1}e_{2}. Let G := ⟨v_{1}, v_{2}, v_{3}, v_{4}⟩ ≤ S_{24}. Then |G| = 36. As in Remark 3.3 we define the face F := F ({e, v_{1}, v_{2}, v_{3}, v_{4}}) of P (G). Now, we check using GAP and polymake that the combinatorial type of F is indeed the dual of W.

(6) P: Let a_{1}, a_{2}, b_{1}, b_{2}, c_{1}, c_{2} be six 3-cycles with pairwise disjoint support, realized as elements in S_{18}. Let e_{1} be an involution that exchanges b_{1} and b_{2}, as before, and e_{2} an involution that exchanges c_{1} and c_{2}. Then we define v_{1} := a_{1}a_{2}, v_{2} := b_{1}b_{2}c_{1}c_{2}, v_{3} := a_{1}b_{1}b_{2}, v_{4} := e_{1}e_{2}. Let G := ⟨v_{1}, v_{2}, v_{3}, v_{4}⟩ ≤ S_{18}. Then |G| = 54. As in Remark 3.3 we define the face F := F ({e, v_{1}, v_{2}, v_{4}}) of P (G). Now, we check that the combinatorial type of F is indeed P.

(7) The wedge over the facet of an octahedron: Let a_{1}, a_{2},b_{1}, b_{2},c_{1}, c_{2},e_{1}, v_{1}, v_{2}, v_{3} be defined as for P. However v_{4} := e_{1}. Then G := ⟨v_{1}, v_{2}, v_{3}, v_{4}⟩ ≤ S_{18} with |G| = 54. We define F as before. Now, we check that the combinatorial type of F is indeed as desired.

(8) Hypersimplex: Let a_{1}, a_{2}, a_{3}, a_{4}, a_{5} be five 3-cycles with pairwise disjoint support, realized as elements in S_{15}. We define v_{1} := a_{1}a_{2}, v_{2} := a_{3}a_{4}, v_{3} := a_{1}a_{3}, v_{4} := a_{1}a_{5}. Let G := ⟨v_{1}, v_{2}, v_{3}, v_{4}⟩ ≤ S_{15}. Then |G| = 81. As in Remark 3.3 we define the face F := F ({e, v_{1}, v_{2}, v_{4}}) of P (G). Then F has dimension five, and we check that F is a pyramid over the hypersimplex.

(9) Q_{1}: We could not find a permutation group G with a face F of P (G) whose combinatorial type coincides with the one of Q_{1}.

(10) Q_{2}: As for Q_{1}. □

Conjecture 4.4. There are no four-dimensional faces of permutation polytopes having the combinatorial type of Q_{1} or Q_{2} (see Table 2).

Remark 4.5. The combinatorics of faces of permutation polytopes is in general much more complex than the one of faces of Birkhoff polytopes. For instance, any facet of a Birkhoff polytope is given as the set of matrices with entry 0 (resp. 1) at a fixed position i, j. Hence, any face of a Birkhoff polytope has the strong property that the vertices in the complement of a facet form a face. In dimension d ≤ 4 all of the polytopes in Theorem 4.3 also possess this property, except the special 0/1-polytopes Q_{1}, Q_{2}, which stresses the exceptional role of these polytopes. However, one should not jump to the wrong conclusion that this might be a necessary condition on a polytope to be a face of a permutation polytope. In dimension d ≥ 9 there are examples of permutation polytopes that have facets whose complement is not even a subset of a proper face, see [6].

5. Open questions and conjectures

5.1. Permutation polytopes. Inspired by an embedding result on Birkhoff faces in [7] we propose the following daring conjecture (in a weak and strong version), where the bound 2d would be sharp as the example of the d-cube shows, see Corollary 3.6. The existence of some bound follows from Proposition 1.3.

Conjecture 5.1. Let P be a d-dimensional permutation polytope. Then there exists a permutation group G ≤ S_{2d} such that P (G) is combinatorially equivalent (or stronger, lattice equivalent) to P.

An even more natural formulation is given be the next conjecture, which was checked for d ≤ 4 using Theorem 4.1. The statement may be phrased purely in terms of representation theory thanks to the dimension formula, see Theorem 2.5.

Conjecture 5.2. Let ρ be a permutation representation of a finite group G with d := dim P (ρ). Then there exists a stably equivalent permutation representation ρ′: G → S_{n} such that n ≤ 2d.

The truth of this statement would imply the weak part of Conjecture 5.1.

The Birkhoff polytope B_{3} is given by the full symmetric group S_{3}. From Theorem 4.1 we observe that S_{3} is essentially the only permutation group having B_{3} as its permutation polytope.

Conjecture 5.3. Let P (G) be a permutation polytope such that P (G) is combinatorially equivalent to the Birkhoff polytope B_{n} for some n. Then the permutation group G is effectively equivalent to S_{n}.

Any element of a permutation group G induces by left, respectively, by right multiplication an affine automorphism of P (G). If G is not abelian, this implies that there are more affine automorphisms of P (G) than elements of G. We conjecture this to be true also in the abelian case, except if |G| ≤ 2.

Conjecture 5.4. Let G be an abelian permutation group of order |G| > 2. Then the group of affine automorphisms of P (G) contains more elements than G.

5.2. Faces of permutation polytopes. Observing the structure of centrally symmetric faces for d ≤ 4 gives rise to the following question.

Question 5.5. Is there a centrally symmetric face of a permutation polytope that is not composable as products or free sums of lower dimensional centrally symmetric faces of permutation polytopes?

It should be true that bipyramids over centrally symmetric faces are again realizable as faces of permutation polytopes. Even more, we expect that it may be possible to generalize the construction of Theorem 3.10.

Conjecture 5.6. The free sum of centrally symmetric faces of permutation polytopes can be combinatorially realized as a face of a permutation polytope.

The next conjecture is based upon explicit checks in low dimensions.

Conjecture 5.7. Let F be a face of a permutation polytope. Then the wedge over a face F′ of F can be combinatorially realized as a face of a permutation polytope, if (or only if) the complement of F′ in F is a face of F.

5.3. Faces of permutation polytopes given by subgroups. It would be interesting to know which subgroups of a permutation group yield faces. One obvious class of such subgroups are stabilizers.

For this let us partition [n] := {1, …, n} = ⨆ I_{i}. Then the polytope of the stabilizer of this partition

stab(G; (I_{i})_{i}) := {σ ∈ G : σ(I_{i}) = I_{i} for all i} ≤ G

is a face of P (G).

Conjecture 5.8. Let G ≤ S_{n}. Suppose H ≤ G is a subgroup such that P (H) ⪯ P (G) is a face. Then H = stab(G; (I_{i})_{i}) for a partition [n] = ⨆ I_{i}.

Proposition 5.9. Conjecture 5.8 holds for G = S_{n} and for G ≤ S_{n} cyclic.

Proof. First, let H ≤ G = S_{n} with P (H) a face of P (G) = B_{n}. Let [n] = ⨆ I_{i} be the orbit partition of H. Then H ≤ stab(G; (I_{i})_{i}) = ∏ S_{I_{i}}. We show that equality holds. The face P (H) ⪯ B_{n}, is the intersection of the facets containing it. For J = {(i, j) : σ(i) ≠ j for all σ ∈ H} that means, cf. Remark 4.5,

P (H) = conv{A ∈ B_{n} : a_{ij} = 0 for all (i, j) ∈ J}.

Because H is transitive on I_{i}, we get J ∩ (I_{i} × I_{i}) = ∅ so that H ≥ ∏ S_{I_{i}}.

Second, let G be a cyclic subgroup of S_{n}, and let H be a subgroup of G. Let G = ⟨g⟩ and let g = g_{1} ∘ ⋯ ∘ g_{r} be the cycle decomposition of g. Then H = ⟨h⟩ for some h = g^{k} = g_{1}^{k} ∘ ⋯ ∘ g_{r}^{k}. If the length of g_{i} is z_{i}, then g_{i}^{k} splits into cycles of length s_{i} := z_{i}/ gcd(z_{i}, k). Let O_{1}, …, O_{l} be the respective orbits of h. Then H stabilizes the partition

[n] = O_{1} ⊔ ⋯ ⊔ O_{l} ⊔ ([n] \ (O_{1} ∪ ... ∪ O_{l})).

Let h′ = g^{t} be another element in G which also stabilizes this partition. This implies z_{i}/ gcd(z_{i}, t) ≤ s_{i}, thus gcd(z_{i}, k) ≤ gcd(z_{i}, t) for i = 1, …, r.

Since k and t divide |G| = o(g) = lcm(z_{1}, …, z_{r}), this yields that k divides t. Hence h′ = g^{t} ∈ H = ⟨g^{k}⟩, and H is the full stabilizer in G of a partition of [n]. □

Acknowledgement. Many of these results are based on extensive calculations using the software packages GAP [17] and polymake [18]. We thank Oswin Aichholzer for providing the list of 0/1-polytopes [1]. The last three authors were supported by Emmy Noether fellowship HA 4383/1 of the German Research Foundation (DFG).

References

[1] Aichholzer, O.: Extremal Properties of 0/1-Polytopes of Dimension 5. In: Kalai, G. (ed.) et al., Polytopes - combinatorics and computation, DMV-seminar Oberwolfach, Germany, November 1997, Basel: Birkhäuser. DMV Semin. 29 111–130, 2000

[2] Aichholzer, O.: Remote computing services via e-mail - 0/1-polytopes. Webpage,

http://www.ist.tugraz.at/staff/aichholzer/research/rp/rcs/info01poly/

(2007)

[3] Athanasiadis, C.A.: Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley. J. Reine Angew. Math. 583, 163–174 (2005)

[4] Balinski, M.L.; Russakoff, A.: On the assignment polytope. SIAM Rev. 16, 516–525 (1974)

[5] Barvinok, A.; Stephen, T.: The distribution of values in the quadratic assignment problem. Math. Oper. Res. 28, 64–91 (2003)

[6] Baumeister, B.; Haase, C.; Nill, B.; Paffenholz, A.: Permutation polytope resource

page. Webpage, http://ehrhart.math.fu-berlin.de/permutations/ (2007)

[7] Billera, L.J.; Sarangarajan, A.: The combinatorics of permutation polytopes. In: Billera, L.J. (ed.) et al., Formal power series and algebraic combinatorics, Séries formelles et combinatoire algébrique 1994, Invited lectures presented at the 6th international DIMACS workshop, May 23-27, 1994, Providence, RI: American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 24, 1–23, 1996

[8] Brandman, J.; Fowler, J.; Lins, B.; Spitkovsky, I.; Zobin, N.: Convex hulls of Coxeter groups. In: Cwikel, M. (ed.) et al., Function spaces, interpolation theory and related topics, Proceedings of the international conference in honour of Jaak Peetre on his 65th birthday, Lund, Sweden, August 17-22, 2000, Berlin: de Gruyter, 213–240, 2002

[9] Breuer, T.; Pfeiffer, G.: Finding possible permutation characters. J. Symb. Comput. 26, 343–354 (1998)

[10] Brualdi, R.A.; Gibson, P.M.: Convex polyhedra of doubly stochastic matrices. I. Applications of the permanent function. J. Comb. Theory, Ser. A 22, 194–230 (1977)

[11] Brualdi, R.A.; Liu, B.: The polytope of even doubly stochastic matrices. J. Comb. Theory, Ser. A 57, 243–253 (1991)

[12] Chan, C.S.; Robbins, D.P.; Yuen, D.S: On the volume of a certain polytope. Exp. Math. 9, 91–99 (2000)

[13] Collins, J.; Perkinson, D.: Frobenius polytopes. Preprint, http://www.reed.edu/

~davidp/homepage/mypapers/frob.pdf (2004)

[14] Curtis, C.W.; Reiner, I.: Representation theory of finite groups and associative algebras. Pure and Applied Math. 11, New York-London: Interscience, 1962

[15] Ellis, G.; Harris, J.; Sköldberg, E.: Polytopal resolutions for finite groups. J. Reine Angew. Math. 598, 131–137 (2006)

[16] Fiedler, M.: Doubly stochastic matrices and optimization. Advances in mathematical optimization, Math. Res. 45, 44–51 (1988)

[17] The GAP Group: GAP – Groups, Algorithms, and Programming, Version 4.4.9.

Webpage, http://www.gap-system.org (2006)

[18] Gawrilow, E.; Joswig, M.: Geometric Reasoning with polymake. Preprint, http:

//arxiv.org/abs/math.CO/0507273 (2005)

[19] Guralnick, R.; Perkinson, D.: Permutation polytopes and indecomposable elements in permutation groups. J. Comb. Theory, Ser. A 113, 1243–1256 (2006)

[20] Hood, J.; Perkinson, D.: Some facets of the polytope of even permutation matrices. Linear Algebra Appl. 381, 237–244 (2004)

[21] Kaibel, V.; Wolff, M.: Simple 0/1-polytopes. Eur. J. Comb. 21, 139–144 (2000)

[22] Onn, S.: Geometry, complexity, and combinatorics of permutation polytopes. J. Comb. Theory, Ser. A 64, 31–49 (1993)

[23] Pak, I.: Four questions on Birkhoff polytopes. Ann. Comb. 4, 83–90 (2000)

[24] Stanley, R.P.: Enumerative Combinatorics, Vol. I. Wadsworth & Brooks/Cole, 1986 [25] Steinkamp, H.: Convex polytopes of permutation matrices. Bachelor thesis, The Di-

vision of Mathematics and Natural Sciences, Reed College, 1999

[26] Tinhofer, G.: Graph isomorphism and theorems of Birkhoff type. Computing 36, 285–300 (1986)

[27] Zeilberger, D.: Proof of a conjecture of Chan, Robbins, and Yuen. Electr. Trans. Num. Anal. 9, 147–148 (1999)

[28] Ziegler, G.M.: Lectures on polytopes. Graduate Texts in Mathematics 152, Berlin: Springer-Verlag, 1995

[29] Ziegler, G.M.: Lectures on 0/1-polytopes. In: Kalai, G. (ed.) et al., Polytopes - combinatorics and computation, DMV-seminar Oberwolfach, Germany, November 1997, Basel: Birkhäuser. DMV Semin. 29, 1–41, 2000

   E-mail address: {baumeist,christian.haase,nill,paffenho}@math.fu-berlin.de

Mathematisches Institut, Freie Universität Berlin, Arnimallee 3, 14195 Berlin, Germany